package com.fosss.sort;


import javax.swing.*;
import java.util.Arrays;
import java.util.Date;

public class HillSort {
    public static void main(String[] args) {
//        int[] arr={9,7,2,6,8,3};
//        System.out.println("排序前的数组->"+ Arrays.toString(arr));
//        hillSort(arr);
//        System.out.println("排序后的数组->"+Arrays.toString(arr));

        //测试时间复杂度
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        long startTime = System.currentTimeMillis();
        hillSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("交换式花费的时间为"+(endTime-startTime)+"毫秒");//4445

//        int[] arr = {9, 7, 2, 6, 8, 3};
//        System.out.println("排序前的数组->" + Arrays.toString(arr));
//        hillSort2(arr);
//        System.out.println("排序后的数组->" + Arrays.toString(arr));


        long startTime2 = System.currentTimeMillis();
        hillSort2(arr);
        long endTime2 = System.currentTimeMillis();
        System.out.println("移动式花费的时间为" + (endTime2 - startTime2) + "毫秒");//3 NEWBEE

    }

    /**
     * 交换式
     *
     * @param arr
     */
    public static void hillSort(int[] arr) {
        int half = 0;//记录分组数
        int temp = 0;//用于交换

        for (half = arr.length; half > 0; half /= 2) {//进行分组
            //将每组分别进行排序
            for (int i = half; i < arr.length; i++) {
                for (int j = i - half; j >= 0; j -= half) {
                    if (arr[j] > arr[j + half]) {
                        temp = arr[j];
                        arr[j] = arr[j + half];
                        arr[j + half] = temp;
                    }
                }
            }

        }


    }

    //移动式
    public static void hillSort2(int[] arr) {
        for (int half = arr.length; half > 0; half /= 2) {

            for (int i = half; i < arr.length; i++) {
                int insertValue = arr[i];
                int insertIndex = i - half;

                while (insertIndex >= 0 && arr[insertIndex] > insertValue) {
                    arr[insertIndex + half] = arr[insertIndex];
                    insertIndex -= half;

                }
                //退出循环说明要插入的位置已经找到，进行插入
                //退出循环说明insertIndex<0,所以需要＋half来恢复为要插入的位置
                arr[insertIndex + half] = insertValue;
            }
        }
    }
}












